
/**
 * 查找充电设备组合
 * 
 * 题目描述

某个充电站，可提供 n 个充电设备，每个充电设备均有对应的输出功率。

任意个充电设备组合的输出功率总和，均构成功率集合 P 的 1 个元素。

功率集合 P 的最优元素，表示最接近充电站最大输出功率 p_max 的元素。

输入描述
输入为 3 行：

第 1 行为充电设备个数 n
第 2 行为每个充电设备的输出功率
第 3 行为充电站最大输出功率 p_max
输出描述
功率集合 P 的最优元素

备注
充电设备个数 n > 0
最优元素必须小于或等于充电站最大输出功率 p_max
用例
输入	4
50 20 20 60
90
输出	90
说明	当充电设备输出功率50、20、20组合时，其输出功率总和为90，最接近充电站最大充电输出功率，因此最优元素为90。
输入	2
50 40
30
输出	0
说明	所有充电设备的输出功率组合，均大于充电站最大充电输出功率30，此时最优元素值为0。

 * 
 */

import java.util.Scanner;

/**
  * 
  题目解析
本题可以当成01背包问题处理。其中：

第3行充电站最大输出功率p_max  可以当成  背包承重
第2行每个充电设备的输出功率  可以当成  不同物品的重量以及价值，即重量 == 价值
现在要求：背包承重下能装入的最大价值。

关于01背包问题，大家可以看算法设计 - 01背包问题_伏城之外的博客-CSDN博客

关于01背包的滚动数组优化解法请看：算法设计 - 01背包问题的状态转移方程优化，以及完全背包问题_01背包问题状态转移方程_伏城之外的博客-CSDN博客

  */
public class 查找充电设备组合 {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
 
        int n = sc.nextInt();
 
        int[] ps = new int[n];
        for (int i = 0; i < n; i++) {
            ps[i] = sc.nextInt();
        }
 
        int p_max = sc.nextInt();
 
        System.out.println(solution(n, ps, p_max));
    }
 
    public static int solution(int n, int[] ps, int p_max) {
        int[][] dp = new int[n + 1][p_max + 1];
 
        for (int i = 1; i <= n; i++) {
            int p = ps[i - 1];
 
            for (int j = 0; j <= p_max; j++) {
                if (j < p) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - p] + p);
                }
            }
        }
 
        return dp[n][p_max];
    }
}
